#include <iostream>
using std::cout;
struct ListNode
{
    int val;
    ListNode *next;
    ListNode() {}
    ListNode(int val, ListNode *next) : val(val), next(next) {}
};

class MyLinkedList
{
public:
    MyLinkedList()
        : _dummy(new ListNode()),
          _listLen(0)
    {
        _dummy->next = nullptr;
        _tail = nullptr;
    }

    int get(int index)
    {
        if (index + 1 > _listLen)
            return -1;
        if (index + 1 == _listLen)
            return _tail->val;
        int cicleNum = index + 1;
        ListNode *cur = _dummy;
        int tmp = 0;
        while (1)
        {
            if (tmp++ > index)
                break;
            cur = cur->next;
        }
        return cur->val;
    }

    void addAtHead(int val)
    {
        ListNode *newNode = new ListNode(val, _dummy->next);
        if (_listLen == 0)
            _tail = newNode;
        _dummy->next = newNode;
        ++_listLen;
    }

    void addAtTail(int val)
    {
        ListNode *newNode = new ListNode(val, nullptr);
        _tail->next = newNode;
        _tail = newNode;
        ++_listLen;
    }

    void addAtIndex(int index, int val)
    {
        if (index == 0)
        {
            addAtHead(val);
            return;
        }
        if (index == _listLen)
        {
            addAtTail(val);
            return;
        }

        ListNode *cur = _dummy;
        int tmp = 0;
        while (1)
        {
            if (tmp++ == index)
            {
                ListNode *newNode = new ListNode(val, cur->next);

                cur->next = newNode;

                ++_listLen;
                break;
            }
            cur = cur->next;
        }
    }

    void deleteAtIndex(int index)
    {
        if(index < 0 || index >= _listLen) return;
        if(index == 0)
        {
            // 删头结点
            ListNode* tmp = _dummy->next;
            _dummy->next = tmp->next;
            delete tmp;
            -- _listLen;
            return;
        }

        int circleNum = 0;
        ListNode* cur = _dummy;
        while(1)
        {
            // 1 2 3
            if(circleNum++ == index)
            {
                // 到达要操作的前一个节点
                if(index == _listLen - 1)
                {
                    delete _tail;
                    _tail = cur;
                    _tail->next = nullptr;
                    -- _listLen;
                    break;
                }
                ListNode* tmp = cur->next;
                cur->next = tmp->next;
                delete tmp;
                -- _listLen;
                break;
            }
            cur = cur->next;
        }
    }

    void print()
    {
        if (_listLen == 0)
        {
            cout << "空链表...\n";
            return;
        }
        ListNode *cur = _dummy;
        while (cur->next != nullptr)
        {
            cur = cur->next;
            if (cur != _tail)
                cout << cur->val << "-->";
            else
                cout << cur->val << "\n";
        }
    }

private:
    ListNode *_dummy;
    ListNode *_tail;
    int _listLen;
};

int main(int argc, char const *argv[])
{
    MyLinkedList mll;
    mll.addAtHead(10);
    mll.addAtHead(20);
    mll.addAtHead(30);
    mll.addAtHead(40);
    mll.addAtTail(50);
    mll.addAtTail(60);
    mll.addAtTail(70);
    mll.addAtTail(80);
    mll.print();
    mll.addAtIndex(2, 22);
    mll.print();
    mll.deleteAtIndex(0);
    mll.print();
    mll.deleteAtIndex(4);
    mll.print();
    getchar();
    return 0;
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */